package leetcode_600;

import java.util.Arrays;

/**
 *@author 周杨
 *NextGreaterElementIII_556 求由相同元素构成的 下一个比其大的数
 *describe:全排列 逆转非递减字符串 AC 80%
 *2018年9月13日 下午2:32:21
 */
public class NextGreaterElementIII_556 {
	 public int nextGreaterElement(int n) {
	        char[] nc = String.valueOf(n).toCharArray();
	        int i,j;
	        for (i = nc.length - 1;i > 0;i--) {
	            if (nc[i - 1] < nc[i]) {
	                break;
	            }
	        }
	        if (i == 0) return -1;//最大的数
	        int x = nc[i - 1], smallest = i;
	        for (j = i + 1;j < nc.length;j++) {
	            if (nc[j] > x && nc[j] <= nc[smallest]) {
	                smallest = j;
	            }
	        }
	        swap(nc,smallest,i - 1);
	        Arrays.sort(nc,i,nc.length);
	        long ans = Long.parseLong(String.valueOf(nc));
	        if (ans <= Integer.MAX_VALUE) return (int)ans;
	        return -1;
	    }
	    private void swap(char[] nc,int i,int j) {
	        char temp = nc[i];
	        nc[i] = nc[j];
	        nc[j] = temp;
	    }
}
